Stack = require("./stack.js");
// 定义运算符优先级
let priorityMap = {
  "+" : 1,
  "-" : 1,
  "*" : 2,
  "/" : 2
};
/**
 * -- 使用栈，完成中序表达式转后续表达式
 * eg:
 * 输入:["12","+", "3"]
 * 输出:["12","3","+"]
 *
 * 输入:["(","1","+","(","4","+","5","+","3",")", "-","3",")","+","(","9","+","8",")"]
 * 输出:[ '1', '4', '5', '+', '3', '+', '+', '3', '-', '9', '8', '+', '+' ]
 *
 * 输入:['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '/', '4', '-', '3', ')', '+', '(', '6', '+', '8', ')', '*', '3']
 * 输出:['1', '4', '5', '+', '3', '+', '4', '/', '+', '3', '-', '6', '8', '+', '3', '*', '+']
 *
 * @author lmay.Zhou
 * @since 2019/4/9 23:22 星期二
 * @qq 379839355
 * @email lmay@lmaye.com
 */
function expressionTransform(exp) {
    let stack = new Stack.Stack();
    let postfixLst = [];

    for(let i=0; i<exp.length; ++i) {
        let item = exp[i];
        if(!isNaN(item)){
            // 如果是数字，直接放入到postfixLst中
            postfixLst.push(item);
        }else if("(" === item) {
            // 遇到左括号入栈
            stack.push(item);
        } else if(")" === item) {
            // 遇到右括号，把栈顶元素弹出，直到遇到左括号
            while ("(" !== stack.top()) {
                postfixLst.push(stack.pop());
            }
            // 左括号出栈
            stack.pop();
        } else {
            // 遇到运算符，把栈顶的运算符弹出，直到栈顶的运算符优先级小于当前运算符
            while(!stack.isEmpty() && ["+", "-", "*", "/"].indexOf(stack.top()) >= 0 && priorityMap[stack.top()] >= priorityMap[item]) {
                // 把弹出的运算符加入到postfixLst中
                postfixLst.push(stack.pop());
            }
            // 当前运算符入栈
            stack.push(item);
        }
    }
    // for循环结束后，栈里可能还有元素，都弹出放入到postfixLst中
    while (!stack.isEmpty()) {
        postfixLst.push(stack.pop());
    }
    return postfixLst;
}

console.log(expressionTransform(["12", "+", "3"]));
console.log(expressionTransform(["(", "1", "+", "(", "4", "+", "5", "+", "3", ")", "-", "3", ")", "+", "(", "9", "+", "8", ")"]));
console.log(expressionTransform(["(", "1", "+", "(", "4", "+", "5", "+", "3", ")", "/", "4", "-", "3", ")", "+", "(", "6", "+", "8", ")", "*", "3"]));